﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Alogrithm
{
    internal class NumberSort
    {
        public static void Bubble(int[] arr)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                for (int j = i + 1; j < arr.Length; j++)
                {
                    //只需要调整为大于号就可以从小到达，目前从大到小
                    if (arr[i] < arr[j])
                    {
                        arr[i] = arr[i] ^ arr[j];
                        arr[j] = arr[j] ^ arr[i];
                        arr[i] = arr[i] ^ arr[j];
                    }
                }
            }
        }

        public static void Insertion(int[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (arr[i] < arr[j])
                    {
                        arr[i] = arr[i] ^ arr[j];
                        arr[j] = arr[j] ^ arr[i];
                        arr[i] = arr[i] ^ arr[j];
                    }
                }
            }
        }

        public static void Merge(int[] arr)
        {
            SplitItem(arr, 0, arr.Length - 1);
        }

        //TODO 这个设计貌似存在问题不应该这样写？如何优化？
        private static void MergeSort(int[] arr, int left, int right, int middle)
        {
            var i1 = left;
            var i2 = middle+1;
            var t = 0;
            var temp = new int[right + 1 - left];
            while (i1<=middle&&i2<=right)
            {
                temp[t++] = arr[i1] <= arr[i2] ? arr[i1++] : arr[i2++];
            }
            while (i1<=middle)
            {
                temp[t++] = arr[i1++];
            }
            while (i2<=right)
            {
                temp[t++] = arr[i2++];
            }
            for (int i = 0; i < temp.Length; i++)
            {
                arr[left + i] = temp[i];
            }
        }

        private static void SplitItem(int[] arr, int left, int right)
        {
            if (left >= right)
            {
                return;
            }
            //这是一个犯的错误，不是right/2;
            var middle = (left + right) / 2;
            SplitItem(arr, left, middle);
            SplitItem(arr, middle + 1, right);
            MergeSort(arr, left, right, middle);
        }
    }
}